🐀 Rat Maze - Find All Paths

Discover all possible paths from start to destination using backtracking with UDLR directions.

🐀 Find All Paths Challenge

The Problem:

A rat is placed at (0, 0) in an N×N maze. Find ALL possible paths to reach (N-1, N-1).

Rules:

  • Maze: N×N matrix (1 = open, 0 = blocked)
  • Start: (0, 0), Goal: (N-1, N-1)
  • Moves: U (up), D (down), L (left), R (right)
  • No cell can be visited twice in same path
  • Return paths in lexicographical order
  • If no path exists, return -1

Input/Output Format

  • Input: N (size), followed by N×N matrix
  • Output: All paths as space-separated strings (e.g., "DDRDRR DRDDRR") or "-1"
  • Constraints: 2 ≤ N ≤ 5, 0 ≤ m[i][j] ≤ 1

Example: 4×4 Maze

Input Maze

S
0
0
0
1
1
0
1
1
1
0
0
0
1
1
E

Output: 2 Paths Found

Path 1: DDRDRR
Path 2: DRDDRR

🔄 Backtracking Algorithm

Algorithm Steps

  1. Initialize: Start at (0,0), mark as visited
  2. Base Case: If at (N-1, N-1), add current path to result
  3. Try All Directions: In order D, L, R, U (lexicographical):
    • Check if move is valid (in bounds, open, not visited)
    • Mark cell as visited, add direction to path
    • Recursively explore from new position
    • Backtrack: unmark cell, remove direction
  4. Sort: Paths automatically sorted due to D→L→R→U order
  5. Return: All paths or "-1" if none found

Key Difference from Single Path

Unlike finding just ONE path, here we:

  • Continue exploring even after finding a path
  • Store ALL successful paths in a list
  • Try directions in lexicographical order: D, L, R, U
  • Must backtrack after each complete path to explore alternatives

Time Complexity

O(4^(N²))
Worst case: 4 choices per cell

Space Complexity

O(N²)
Visited matrix + recursion stack

Direction Priority (Lexicographical Order)

  • D (Down): row + 1, same column
  • L (Left): same row, column - 1
  • R (Right): same row, column + 1
  • U (Up): row - 1, same column

This order ensures paths are generated in lexicographical order automatically!

🔍 Step-by-Step Path Finding

Ready. Load a maze to start demo.

Maze Visualization

Start
Goal
Current
Path
Wall
Load maze to begin

Progress Tracker

1. Parse maze input
2. Initialize visited matrix
3. Start at (0,0)
4. Explore paths (D→L→R→U)
5. Record complete paths
6. Return all paths or -1

🎮 Solve Your Own Maze

Enter maze and press Find All Paths

Test Cases

Sample 1
4×4 maze → Output: DDRDRR DRDDRR
Sample 2
2×2 blocked → Output: -1
Sample 3
3×3 maze → Output: RDDR

📊 Algorithm Analysis

Time

O(4^(N²))

Worst case explores all possibilities

Space

O(N²)

Visited matrix + recursion

Complexity Breakdown

  • Time: Up to 4 directions per cell, N² cells → O(4^(N²))
  • Space: Visited matrix O(N²) + path string + recursion depth O(N²)
  • Practical: Much faster due to walls and visited cells pruning search space
  • Paths: Number of valid paths varies greatly based on maze structure

Why This Approach?

  • Backtracking naturally explores all possibilities
  • Lexicographical order achieved by trying D→L→R→U
  • Visited matrix prevents cycles within a single path
  • Backtracking allows exploring alternative routes

Key Implementation Points

  1. Mark cell as visited before exploring
  2. Unmark after returning (backtracking)
  3. Try directions in exact order: D, L, R, U
  4. Store complete path when reaching goal
  5. Continue exploring to find all paths
  6. Return sorted list (already sorted if directions ordered correctly)

Real-World Applications

  • Robotics: Finding all possible navigation routes
  • Games: Pathfinding with multiple solutions
  • Network Routing: Discovering redundant paths
  • Circuit Design: Multiple routing possibilities